package pers.qianyu.month_202012.date_20201212;

import org.junit.*;

import java.util.*;

/**
 * 84. 柱状图中最大的矩形
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 *
 * @author mizzle rain
 * @date 2020-12-12 22:50
 */
public class LargestRectangleArea {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        int area = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                int h = heights[stack.removeLast()];
                int w;
                if (stack.isEmpty()) {
                    w = i;
                } else {
                    w = i - stack.peekLast() - 1;
                }
                area = Math.max(w * h, area);
            }
            stack.addLast(i);
        }
        while (!stack.isEmpty()) {
            int h = heights[stack.removeLast()];
            int w;
            if (stack.isEmpty()) {
                w = len;
            } else {
                w = len - stack.peekLast() - 1;
            }
            area = Math.max(w * h, area);
        }
        return area;
    }

    @Test
    public void test1() {
        int[] arr = {2, 1, 5, 6, 2, 3};
        int result = new LargestRectangleArea().largestRectangleArea(arr);
        System.out.println("result = " + result);
    }
}
